#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>

using namespace std;
using PII = pair<int, int>;

const int N = 1e5 + 10;

int n, m;
int q[N];
int nums[N];

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int T;
    scanf("%d", &T);

    while(T--){
        map<PII, bool> mp;
        memset(nums, 0, sizeof nums);
        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; i ++){
            scanf("%d", &q[i]);
        }

        for (int i = 1; i <= m; i ++){
            int a, b;
            scanf("%d%d", &a, &b);
            nums[a]++;
            nums[b]++;
            PII t = {a, b};
            mp[t] = true;
        }

        if(m % 2 == 0){
            printf("0\n");
        }else{
            int minV = 1e9 + 10;
            for (int i = 1; i <= n; i ++){
                if(nums[i] % 2 == 1 && minV > q[i]){
                    minV = q[i];
                }
            }


            for (auto &t : mp)
            {
                PII temp = t.first;
                // cout << "x : " << temp.first << " y : " << temp.second << endl;
                if (((nums[temp.first] + nums[temp.second]) % 2) == 0)
                {
                    minV = min(minV, q[temp.first] + q[temp.second]);
                }
                }

            printf("%d\n", minV);
        }
    }

    return 0;
}